#include <iostream>
#include <cstdio>
using namespace std;
void QuickSort(int [],int,int);
int getArrayk(int array[],int k,int arrlen);
void printArray(int *,int);

/**
	排序作业-a
	在O(n)的时间复杂度下求得无序数组经排序后的第K位数据
*/

int main()
{
	int a[10] = {11,123,2,2,66,11,888,55,124,555};
	int len = sizeof(a)/sizeof(int);
	cout << "排序前：" << endl;
	printArray(a,len);
	int inp = 0;
	//输入要找第K大的数字 
	printf("input a value < %d\n",len);
	scanf("%d",&inp); 
	//找到第K大的数字 
	int k = getArrayk(a,inp,len);
	printf("第%d大的数是: %d",inp,k);
	cout << "\n\n排序后(快速排序)：" << endl;
	printArray(a,len);
	return 0;
}

/**
	排序作业-a (getArrayk)
	在O(n)的时间复杂度下求得无序数组经排序后的第K位数据
*/
int getArrayk(int array[],int k,int arrlen){
	if (k > arrlen){
		return -1;
	}
	int temp = 0;
	int num = 0;
	QuickSort(array,0,arrlen-1);
	for (int i = 0;i<arrlen;i++){
		int arrnum = array[i];
		if (num<arrnum) {
			temp++;
			num = arrnum;
		}
		if (temp>=k){
			return num;
		}
	}
}

/**
	快速排序 
*/
void QuickSort(int a[], int left, int right) 
{
    int i,j,temp;
    if(left > right)
        return;
    temp = a[left];//temp中存着基准数
    i = left;
    j = right;
    while(i < j)
	{
        //从右往左找
        while(a[j] >= temp &&i < j)
            j--;
        //从左往右找比
        while(a[i] <= temp && i < j)
            i++;
        //交换两个数
        if(i < j){
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    //基准数归位
    a[left] = a[i];
    a[i] = temp;

    QuickSort(a,left,i - 1);//递归左边
    QuickSort(a,i + 1,right);//递归右边
}

/**
	输出数组 
*/
void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}
